/*
 * tci 2002 semi 3 prob 1
 */

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;


public class Travel
{
    double[] getR (String city) {
	double[] ans = new double[2];
	String[] tmp = city.split (" ");
	ans[0] = Double.parseDouble (tmp[0]);
	ans[1] = Double.parseDouble (tmp[1]);
	
	ans[0] = Math.toRadians (ans[0]);
	ans[1] = Math.toRadians (ans[1]);
	return ans;
    }
    
    
    double[] getC (int r, double[] a) {
	double[] ans = new double[3];
	ans[0] = r * Math.cos (a[0]) * Math.cos (a[1]);
	ans[1] = r * Math.cos (a[0]) * Math.sin (a[1]);
	ans[2] = r * Math.sin (a[0]);
	return ans;
    }
    
    double getDis (double[] c1, double[] c2, double r) {
	double d = 0;
	for (int i = 0; i < 3; ++i)
	    d += Math.pow ((c1[i] - c2[i]), 2);
	d = Math.sqrt (d);
	return 2*r*Math.asin (d/(2*r));
    }
    
    
    public int shortest(String[] cities, int radius)
    {
	int n = cities.length;
	double[][] c = new double[n][3];
	for (int i = 0; i < n; ++i) 
	    c[i] = getC (radius, getR (cities[i]));
	
	double[][] dis = new double[n][n];
	for (int i = 0; i < n; ++i)
	    for (int j = i+1; j < n; ++j) 
		dis[j][i] = dis[i][j] = getDis (c[i], c[j], radius);
	
	/* dfs. */
	double[][] h = new double[n][1<<n];
	for (int i = 0; i < n; ++i)
	    Arrays.fill (h[i], Double.MAX_VALUE);
	h[0][1<<0] = 0;
	LinkedList<Integer> stack1 = new LinkedList<Integer> ();
	LinkedList<Integer> stack2 = new LinkedList<Integer> ();
	stack1.addLast (0);
	stack2.addLast (1<<0);
	while (!stack1.isEmpty ()) {
	    int cur = stack1.removeLast ();
	    int curState = stack2.removeLast ();
	    
	    for (int k = 0; k < n; ++k) {
		int nextState = curState | (1<<k);
		double nextD = h[cur][curState] + dis[cur][k];
		if (h[k][nextState] > nextD) {
		    stack1.addLast (k);
		    stack2.addLast (nextState);
		    h[k][nextState] = nextD;
		}
	    }
	}
	return (int)(h[0][(1<<n)-1] + 0.5);
    }
    
    <%:testing-code%>
}
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!